package data_structure.test;


/**
 * 双向循环链表实现约瑟夫问题
 * 约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
 * 例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。
 * 首先A开始报数，他报1。侥幸逃过一劫。
 * 然后轮到B报数，他报2。非常惨，他被杀了
 * C接着从1开始报数
 * 接着轮到A报数，他报2。也被杀死了。
 * 最终胜利者是C
 */
class BidirectionalCircularLinkedList {
    //头结点
    //双向循环链表 头结点的尾指针 指向 头结点的头指针
    private static Person head = new Person(null,"",null);
    public static int size = 0;
    //测试
    public static void main(String[] args) {
        BidirectionalCircularLinkedList account = new BidirectionalCircularLinkedList();
        Person p1 = new Person(null,"张三",null);
        Person p2 = new Person(null,"李四",null);
        Person p3 = new Person(null,"王五",null);
        account.insert(p1);
        account.insert(p2);
        account.insert(p3);
        account.select();
        System.out.println("初始化完成...");
        account.josephRing(2);
        account.select();
    }

    //解决约瑟夫环问题
    public void josephRing(int index){
        Person temp = head;
        int count = 1;
        while (head.next != head && size >= 1){
            while (count != index) {
                temp = temp.next;
                count++;
            }
            if (count == index) {
                //找到对应位置并删除
                System.out.println("删除名称: "+temp.value);
                delete(temp.value);
                temp = temp.next;
            }
            count = 1;
        }
    }

    //添加
    public void insert(Person person){
        //首先判断链表是否为空 即head.next是否为空
        if (head.next == null){
            head = person;
            head.next = head;
            head.pre = head;
            size++;
            return;
        }
        //temp 作为指针
        Person temp = head;
        while (temp.next != head){
            temp = temp.next;
        }
        //此处有 bug ！
        head.pre = person;
        temp.next = person;
        person.pre = temp;
        person.next = head;
        size++;
    }

    //遍历
    public void select(){
        Person temp = head;
        System.out.println(temp);
        while (temp.next != head){
            temp = temp.next;
            System.out.println(temp);
        }
    }

    //删除结点 根据姓名删除
    public void delete(String name){
        Person temp = head;
        //如果是头结点
        if (temp.value.equals(name)){
            head = head.next;
            delete(name);
        }
        while (temp.next != head){
            if (temp.next.value.equals(name)){
               //这边应该找到 对应结点的前一个结点
                Person preTemp = temp.next.next;
                temp.next = preTemp;
                preTemp.pre = temp;
                break;
            }
            temp = temp.next;
        }
        size--;
    }

    //实体类
    static class Person{
        private Person pre;
        private String value;
        private Person next;

        public Person(Person pre, String value, Person next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Person{" +
                    "value='" + value + '\'' +
                    '}';
        }
    }
}


